#include <string>
using namespace std;

class Solution {
public:
    string reorganizeString(string S) {
        int count[26];
        for (int i = 0; i < 26; i++)
            count[i] = 0;
        int max = 0;
        for (char c : S) {
            if (max < ++count[c - 'a'])
                max = count[c - 'a'];
        }
        if (max > (S.length() + 1) / 2)
            return "";
        string res = S;
        int odd = 1, even = 0;
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0 && count[i]<=S.length()/2&&odd < S.length()) {
                res[odd] = 'a' + i;
                count[i]--;
                odd += 2;
            }
            while (count[i] > 0&&even<S.length()) {
                res[even] = 'a' + i;
                count[i]--;
                even += 2;
            }
        }
        return res;
    }
};